//剑指offer65，矩阵中的路径
//与第66题思路大致，都是dfs查找，
public class Solution{
	boolean[][] tag;//必须定义为全局变量，这样所有的方法才能访问
	//tag用来标记已经走过的位置
	public boolean hasPath(char[] martix,int rows,int cols,char[] str){
		tag=char[rows][cols];
		char[][] tmp=new char[rows][cols];
		for(int i=0;i<rows;i++){
			for(int j=0;j<cols;j++){
				tmp[i][j]=martix[i*cols+j];//将martix这个一维数组转换为二维数组
			}
		}
		for(int i=0;i<rows;i++){
			for(int j=0;j<cols;j++){
				if(find(tmp,rows,cols,str,i,j,0)){//遍历二位数组中的每一个数，进行dfs
					return true;
				}
			}
		}
	return false;
	}
	public boolean find(char[][] tmp,int rows,int cols,char[] str,int row,int col,int index){
		if(index>=str.length){
			return true;//特殊情况，全部遍历完
		}
		if(row<0||col<0||row>=row||col>=cols||tmp[row][col]!=str[index]||tag[row][col]==true){
			return false;//这些情况，返回false
		}
		tag[row][col]=true;//防止同一个位置多次使用。Eg："ABCESFCSADEE",3,4,"ABCB"这里B重复使用了
		boolean isFind=find(tmp,rows,cols,str,row+1,col,index+1)
		||find(tmp,rows,cols,str,row-1,col,index+1)
		||find(tmp,rows,cols,str,row,col+1,index+1)
		||find(tmp,rows,cols,str,row,col-1,index+1);
		tag[row][col]=false;//保护现场，在退出的时候确保tag数组中全为false，以便下次遍历使用
		return isFind;
	}
}